package crypt_kicker;

import java.util.*;

public class Crypt_Kicker 
{
	public static void main(String [] args)
	{
		String [] encryption = {"bjvg", "xsb", "hxsn", "xsb", "qymm", "xsb", "rqat", "xsb", "pnetfn"};
		String [] dictionary = {"and", "dick", "jane", "puff", "spot", "yertle"};
		String [] solArray = new String[encryption.length + 1];
		
		TreeMap<String, String> map = new TreeMap<String, String>();
		
		for (int i = 0; i < encryption.length; i++)
		{
			String word = encryption[i];
				for (int x = 0; x < word.length(); x++)
				{
					String ch = word.substring(x, x+1);
					
					if (!map.containsKey(ch))
					{
						map.put(ch, null);
					}
				}
		}
		
		cryptTrack(solArray, 0, dictionary, encryption, map);
	}
	
	/*
	 * A backtracking solution for crypt kicker. 
	 */
	public static void cryptTrack(String [] solArray, int k, String [] dictionary, String [] encryptWord, TreeMap<String, String> alphaMap)
	{
		// Construct candidates for next position.
		String [] candidates = new String[dictionary.length];
		String word = "";
		
		if (k < encryptWord.length)
		{
			word = encryptWord[k];
		}
		
		// Possible candidate count for next position.
		int numOfCandidates = deterNumOfCandidates(word, dictionary);
		
		int index;
		
		boolean result = false;
		
		if (isSolution(solArray,k,alphaMap))
			printSolution(solArray);
		else 
		{
			k++;
			
			constructCandidates(candidates, dictionary, word);
			
			for (index = 0; index < numOfCandidates; index++)
			{
					solArray[k] = candidates[index];
				
					result = makeMove(solArray, k, word, alphaMap);
					
					if (result == true)
					{
						cryptTrack(solArray,k, dictionary, encryptWord, alphaMap);
					} else {
						unMakeMove(solArray, k, word, encryptWord, alphaMap); 
					}
			}
		}
			
	}
	
	public static int deterNumOfCandidates(String selectedWord, String [] dictionary)
	{
		int count = 0;
		
		for (int i = 0; i < dictionary.length; i++)
		{
			if (dictionary[i].length() == selectedWord.length())
			{
				count++;
			}
		}
		return count;
	}
	
	public static void constructCandidates(String[] candidates, String[] dictionary, String encryptWord) 
	{
		int x = 0;
		
		for (int i = 0; i < dictionary.length; i++)
		{
			if (dictionary[i].length() == encryptWord.length())
			{
				candidates[x] = dictionary[i];
				x++;
			}
		}
	}
	
	public static boolean makeMove(String [] solArray, int k, String eWord, TreeMap<String, String> map)
	{
		// Verify that the elements in solution array has a correct one-to-one mapping with the tree map.
		String word = solArray[k];
		
		boolean result = true;
		
		for (int index = 0; index < word.length(); index++)
		{
			// Take the character of the selected dictionary word.
			String character = word.substring(index, index + 1);
			
			// Take the character of the encryption word.
			String eCharacter = eWord.substring(index, index + 1);
			
			// Retrieve value using character of encryption word as key.
			String value = map.get(eCharacter);
			
			if (value != null)
			{
				if (value.equals(character))
				{
					result = true;
				} 
				else 
				{
					return !result;
				}
			} 
		}
		
		if (result == true)
		{
			// Map the characters.
			for (int index = 0; index < word.length(); index++)
			{
				// Take the character of the encryption word.
				String eCharacter = eWord.substring(index, index + 1);
				
				// Take the character of the selected dictionary word.
				String character = word.substring(index, index + 1);
				
				map.put(eCharacter, character);
			}
		}
			return result;
	}
	
	public static void unMakeMove(String [] solArray, int k , String word, String [] encryptWord, TreeMap<String, String> map)
	{	
		int length = 0;
		
		// Reset portion of tree map. 
		for (int i = 0; i < k - 1; i++)
		{
			String eWord = encryptWord[i];
			
				if (eWord.length() <= word.length())
				{
					length = eWord.length();
				} else {
					length = word.length();
				}
				
				for (int j = 0; j < length; j++)
				{
					String eChar = eWord.substring(j, j+1);
					String wChar = word.substring(j, j+1);
					
					if (!eChar.equals(wChar))
					{
						// reset
						map.put(wChar, null);
					}
				}
		}
		
		// Set word to null.
		solArray[k] = null;
	}
	
	
	public static boolean isSolution(String[] solArray, int k, TreeMap<String, String> AlphaMap) 
	{
		boolean done = false;
		
		// Verify that the solution array is filled.
		for (int index = 1; index < solArray.length; index++)
		{
			if (solArray[index] == null)
			{
				return false;
			}
		}
		
		return true;
	}
	
	public static void printSolution(String [] solArray)
	{
		for (int i = 1; i < solArray.length; i++)
		{
			System.out.print(solArray[i] + " ");
		}
		System.out.println();
	}
}
